//-------------------------------------------------------------------
// Purpose: Demonstrate a collection of recursive functions.
//
// Fast functions
// 	O(logN)         binary_search(array, 1, N)
// 	O(logN)         power(X, N)
// 
// Average functions
// 	O(N)            factorial(N)
// 	O(N)            flood_fill(N pixel)
// 	O(N)            identifier(N chars)
// 	O(N)            list_print(N nodes)
// 	O(N)            palindrome(string, 1, N)
// 	O(N)            reverse(array, 1, N)
// 	O(N)            sum_squares(1, N)
// 
// Slow functions
// 	O(2^N)          fibonacci(N)
// 	O(2^N)          tower-of-hanoi(N)
// 	O(N!)           n-queens(N)
// 	O(huge)         ackerman(M, N)
//
// Author:  John Gauch
//-------------------------------------------------------------------

#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
bool TRACE = false;

//-------------------------------------------------------------------
int factorial(int num)
{
   if (TRACE) cout << "Entering factorial " << num << endl;
   int result = 0;

   // Check terminating conditions
   if (num <= 1)
      result = 1;

   // Handle recursive case
   else
      result = num * factorial(num - 1);

   if (TRACE) cout << "Leaving factorial " << num << endl;
   return result;
}

//-------------------------------------------------------------------
void test_factorial()
{
   cout << "\nTesting factorial\n";

   // Calling function
   for (int i = -1; i <= 10; i++)
      cout << "factorial(" << i << ") = " << factorial(i) << endl;
}

//-------------------------------------------------------------------
int sum_squares(int low, int high)
{
   if (TRACE) cout << "Entering sum_squares " << low << " " << high << endl;
   int result = 0;

   // Check terminating conditions
   if (low > high)
      result = 0;
   else if (low == high)
      result = low * low;

   // Handle recursive case
   else
   {
      int mid = (low + high) / 2;
      result = sum_squares(low, mid) + sum_squares(mid+1, high);
   }

   if (TRACE) cout << "Leaving sum_squares " << low << " " << high << endl;
   return result;
}

//-------------------------------------------------------------------
void test_sum_squares()
{
   cout << "\nTesting sum_squares\n";

   // Calling function
   cout << "sum_squares(2,1) = " << sum_squares(2,1) << endl;
   cout << "sum_squares(0,0) = " << sum_squares(0,0) << endl;
   cout << "sum_squares(1,1) = " << sum_squares(1,1) << endl;
   for (int i = 2; i <= 10; i++)
      cout << "sum_squares(" << i << "," << 2*i << ") = " << sum_squares(i,2*i) << endl;
}

//-------------------------------------------------------------------
float power(float x, int p)
{
   if (TRACE) cout << "Entering power " << x << " " << p << endl;
   float result = 0;

   // Check terminating conditions
   if (p == 0)
      result = 1;

   else if (p == 1)
      result = x;

   // Handle recursive cases
   else if (p < 0)
   {
      result = 1 / power(x, -p);
   }
   else if (p % 2 == 0)
   {
      float temp = power(x, p / 2);
      result = temp * temp;
   }
   else if (p % 2 == 1)
   {
      float temp = power(x, p / 2);
      result = x * temp * temp;
   }

   if (TRACE) cout << "Leaving power " << x << " " << p << endl;
   return result;
}

//-------------------------------------------------------------------
void test_power()
{
   cout << "\nTesting power\n";

   // Calling function
   for (int i = -2; i <= 10; i++)
      cout << "power(" << 2 << "," << i << ") = " << power(2,i) << endl;
}

//-------------------------------------------------------------------
int fibonacci(int num)
{
   if (TRACE) cout << "Entering fibonacci " << num << endl;
   int result = 0;

   // Check terminating condition
   if (num <= 2)
      result = 1;

   // Handle recursive case
   else
      result = fibonacci(num - 1) + fibonacci(num - 2);

   if (TRACE) cout << "Leaving fibonacci " << num << endl;
   return result;
}

//-------------------------------------------------------------------
void test_fibonacci()
{
   cout << "\nTesting fibonacci\n";

   // Calling function
   for (int i = -1; i <= 10; i++)
      cout << "fibonacci(" << i << ") = " << fibonacci(i) << endl;
}

//-------------------------------------------------------------------
int ackerman(int m, int n)
{
   if (TRACE) cout << "Entering ackerman " << m << " " << n << endl;
   int result = 0;

   // Check terminating conditions
   if ((m < 0) || (n < 0))
      result = 0;

   else if (m == 0)
      result = n + 1;

   // Handle simple recursive case 
   else if (n == 0)
      result = ackerman(m - 1, 1);

   // Handle messy recursive case
   else
   {
      int temp = ackerman(m, n - 1);
      result = ackerman(m - 1, temp);
   }

   if (TRACE) cout << "Leaving ackerman " << m << " " << n << endl;
   return result;
}

//-------------------------------------------------------------------
void test_ackerman()
{
   cout << "\nTesting ackerman\n";

   // Calling function
   cout << "ackerman(0,-1) = " << ackerman(0,-1) << endl;
   cout << "ackerman(-1,0) = " << ackerman(-1,0) << endl;
   cout << "ackerman(0,0) = " << ackerman(0,0) << endl;
   cout << "ackerman(0,1) = " << ackerman(0,1) << endl;
   for (int i = 1; i <= 3; i++)
   for (int j = 1; j <= 2*i; j++)
      cout << "ackerman(" << i << "," << j << ") = " << ackerman(i,j) << endl;
   // cout << "ackerman(4,1) = " << ackerman(4,1) << endl;
}

//-------------------------------------------------------------------
void reverse(int data[], int low, int high)
{
   if (TRACE) cout << "Entering reverse " << low << " " << high << endl;

   // Check terminating condition
   if (low >= high)
      return;

   // Handle recursive case
   else
   {
      int temp = data[low];
      data[low] = data[high];
      data[high] = temp;
      reverse(data, low + 1, high - 1);
   }

   if (TRACE) cout << "Leaving reverse " << low << " " << high << endl;
}

//-------------------------------------------------------------------
void test_reverse()
{
   cout << "\nTesting reverse\n";
   int data[10] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
   cout << "data = ";
   for (int i = 0; i < 10; i++)
      cout << data[i] << " ";
   cout << endl;

   // Calling function
   for (int s = 0; s <= 9; s++)
   {
      cout << "reverse(data," << s << ",9)\n";
      reverse(data,s,9);
      cout << "data = ";
      for (int i = 0; i < 10; i++)
         cout << data[i] << " ";
      cout << endl;
   }
}

//-------------------------------------------------------------------
int search(int data[], int value, int low, int high)
{
   if (TRACE) cout << "Entering search " << value << " " << low << " " << high << endl;
   int result = 0;
   int mid = (low + high) / 2;

   // Check terminating conditions
   if (low > high)
      result = -1;

   else if (data[mid] == value)
      result = mid;

   // Handle recursive cases
   else if (data[mid] > value)
      result = search(data, value, low, mid - 1);

   else if (data[mid] < value)
      result = search(data, value, mid + 1, high);

   if (TRACE) cout << "Leaving search " << value << " " << low << " " << high << endl;
   return result;
}

//-------------------------------------------------------------------
int search2(vector<int> & data, int value, int low, int high)
{
   if (TRACE) cout << "Entering search2 " << value << " " << low << " " << high << endl;
   int result = 0;
   int mid = (low + high) / 2;

   // Check terminating conditions
   if (low > high)
      result = -1;

   else if (data[mid] == value)
      result = mid;

   // Handle recursive cases
   else if (data[mid] > value)
      result = search2(data, value, low, mid - 1);

   else if (data[mid] < value)
      result = search2(data, value, mid + 1, high);

   if (TRACE) cout << "Leaving search2 " << value << " " << low << " " << high << endl;
   return result;
}

//-------------------------------------------------------------------
int search3(int Data[], int Desired, int Min, int Max)
{
   // Search array using divide and conquer approach
   int Mid = (Min + Max) / 2;
   if (TRACE) cout << "Min Max Mid " << Min << " " << Max << " " << Mid << endl;
   while ((Min <= Max) && (Data[Mid] != Desired))
   {
      // Change min to search right half
      if (Data[Mid] < Desired)
         Min = Mid+1;

      // Change max to search left half
      else if (Data[Mid] > Desired)
         Max = Mid-1;

      // Update mid location
      Mid = (Min + Max) / 2;
      if (TRACE) cout << "Min Max Mid " << Min << " " << Max << " " << Mid << endl;
   }

   // Return results of search
   if ((Min <= Max) && (Data[Mid] == Desired))
      return(Mid);
   else
      return(-1);
}

//-------------------------------------------------------------------
void test_search()
{
   cout << "\nTesting search\n";
   const int SIZE = 10;
   int data[SIZE] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
   cout << "data = ";
   for (int i = 0; i < SIZE; i++)
      cout << data[i] << " ";
   cout << endl;

   // Calling function
   for (int i = 1; i <= 21; i++)
      cout << "search(data," << i << ",0,10) = " << search(data,i,0,SIZE) << endl;
}

//-------------------------------------------------------------------
void test_search2()
{
   cout << "\nTesting search2\n";
   vector<int> data;
   for (int i=2; i<=20; i=i+2)
      data.push_back(i);

   cout << "data = ";
   for (int i = 0; i < 10; i++)
      cout << data[i] << " ";
   cout << endl;

   // Calling function
   for (int i = 1; i <= 21; i++)
      cout << "search2(data," << i << ",0,9) = " << search2(data,i,0,9) << endl;
}

//-------------------------------------------------------------------
bool palindrome(string input, int low, int high)
{
   if (TRACE) cout << "Entering palindrome " << low << " " << high << endl;
   bool result = false;

   // Handle single char case
   if ((high-low == 0) || (high-low == 1))
      result = true;

   // Handle recursive case
   else if ((low < high) && (input[low] == input[high]))
      result = (palindrome(input, low + 1, high - 1));

   // Otherwise no palindrom        
   else
      result = false;

   if (TRACE) cout << "Leaving palindrome " << low << " " << high << endl;
   return result;
}

//-------------------------------------------------------------------
void test_palindrome()
{
   cout << "\nTesting palindrome\n";

   // Calling function
   string input[5] = { "", "a", "radar", "hello", "neveroddoreven" };
   for (int i = 0; i < 5; i++)
   {
      cout << "palindrome(" << input[i] << ",0," << int(input[i].length()-1) << ") = " 
           << palindrome(input[i], 0, input[i].length()-1) << endl;
   }
}

//-------------------------------------------------------------------
void tower(int count, char src, char dest, char extra)
{
   // Handle recursive case
   if (count > 0)
   {
      tower(count - 1, src, extra, dest);
      cout << "move disk from " << src << " to " << dest << endl;
      tower(count - 1, extra, dest, src);
   }
}

//-------------------------------------------------------------------
void test_tower()
{
   cout << "\nTesting tower\n";

   // User input
   int cnt;
   cout << "enter count ";
   cin >> cnt;
   
   // Calling function
   for (int i = 0; i <= cnt; i++)
   {
      cout << "calling tower(" << i << ", 'A', 'B', 'C')\n";
      tower(i, 'A', 'B', 'C');
   }
}

//-------------------------------------------------------------------
int STEP = 0;
int SOLUTION = 0;
const int SIZE = 8;

//-------------------------------------------------------------------
void clear_board(char board[SIZE][SIZE])
{
   STEP = 0;
   SOLUTION = 0;
   for (int r = 0; r < SIZE; r++)
   for (int c = 0; c < SIZE; c++)
      board[r][c] = '.';
}

//-------------------------------------------------------------------
void print_board(char board[SIZE][SIZE])
{
   // Print chess board
   cout << "+";
   for (int x = 0; x < SIZE; x++)
      cout << "--";
   cout << "-+\n";
   for (int r = 0; r < SIZE; r++)
   {
      cout << "|";
      for (int c = 0; c < SIZE; c++)
         cout << " " << board[r][c] ;
      cout << " |\n";
   }
   cout << "+";
   for (int x = 0; x < SIZE; x++)
      cout << "--";
   cout << "-+\n";
}

//-------------------------------------------------------------------
bool safe(char board[SIZE][SIZE], int row, int col)
{
   // Check coordinates
   if ((row < 0) || (row >= SIZE) || (col < 0) || (col >= SIZE))
      return false;

   // Check row for Q
   for (int c = 0; c < SIZE; c++)
      if (board[row][c] == 'Q')
         return false;

   // Check col for Q
   for (int r = 0; r < SIZE; r++)
      if (board[r][col] == 'Q')
         return false;

   // Check diagonals for Q
   for (int d = 0; d < SIZE; d++)
   {
      if ((row+d < SIZE) && (col+d < SIZE) && (board[row+d][col+d] == 'Q'))
         return false;
      if ((row+d < SIZE) && (col-d >= 0) && (board[row+d][col-d] == 'Q'))
         return false;
      if ((row-d >= 0) && (col+d < SIZE) && (board[row-d][col+d] == 'Q'))
         return false;
      if ((row-d >= 0) && (col-d >= 0) && (board[row-d][col-d] == 'Q'))
         return false;
   }

   // Otherwise safe
   return true;
}

//-------------------------------------------------------------------
bool queen(char board[SIZE][SIZE], int col, bool stop)
{
   // Check terminating condition
   if (col >= SIZE)
   {
      cout << "Solution: " << ++SOLUTION << endl;
      print_board(board);
      return stop;
   }

   // Handle recursive case
   else				
   {
      // Try all possible rows
      for (int row = 0; row < SIZE; row++)
      {
         // Check if location is safe
	 if (safe(board, row, col))
	 {
            // Place Q
	    board[row][col] = 'Q';
            // print_board(board);
            // cout << "Step: " << ++STEP << endl;

            // Check next col
	    if (queen(board, col + 1, stop))
	       return true;

            // Remove Q
	    else
	       board[row][col] = '.';
	 }
      }

      // Return false if no solution found
      return false;
   }
}

//-------------------------------------------------------------------
void slow_queen(char board[SIZE][SIZE])
{
   // Loop over all positions for 8 queens
   long count = 0;
   long solution = 0;
   for (int r0=0; r0<8; r0++)
   for (int r1=0; r1<8; r1++)
   for (int r2=0; r2<8; r2++)
   for (int r3=0; r3<8; r3++)
   for (int r4=0; r4<8; r4++)
   for (int r5=0; r5<8; r5++)
   for (int r6=0; r6<8; r6++)
   for (int r7=0; r7<8; r7++)
   {
      // Check for valid board configuration
      count++;
      clear_board(board);
      if (safe(board, r0,0)) { board[r0][0] = 'Q';
      if (safe(board, r1,1)) { board[r1][1] = 'Q';
      if (safe(board, r2,2)) { board[r2][2] = 'Q';
      if (safe(board, r3,3)) { board[r3][3] = 'Q';
      if (safe(board, r4,4)) { board[r4][4] = 'Q';
      if (safe(board, r5,5)) { board[r5][5] = 'Q';
      if (safe(board, r6,6)) { board[r6][6] = 'Q';
      if (safe(board, r7,7)) { board[r7][7] = 'Q';
      cout << "Solution: " << ++solution << " Count: " << count << endl;
      print_board(board); }}}}}}}}
   }
   cout << "Final count: " << count << endl;
}

//-------------------------------------------------------------------
void test_queen()
{
   cout << "\nTesting queen\n";
   char board[SIZE][SIZE];

   // Calling slow iterative function to find ALL solutions
   clear_board(board);
   slow_queen(board);

   // Calling fast recursive function to find ALL solutions
   // clear_board(board);
   // queen(board, 0, false);
}

//-------------------------------------------------------------------
struct Node
{
   int value;
   Node * next;
};

void list_print(Node * ptr)
{
   // Handle terminating condition
   if (ptr == NULL)
      return;

   // Print value
   cout << "value = " << ptr->value << endl;

   // Handle recursion
   list_print(ptr->next);
}

//-------------------------------------------------------------------
void test_list_print()
{
   cout << "\nTesting list_print\n";

   // Calling function
   Node *head = NULL;
   for (int i = 0; i < 7; i++)
   {
      Node *temp = new Node();
      temp->value = i * 7;
      temp->next = head;
      head = temp;
   }
   list_print(head);
}

//-------------------------------------------------------------------
bool identifier(string input, int pos)
{
   // Handle single char case
   if ((pos == 0) && isalpha(input[pos]))
      return true;

   // Handle recursive case
   else if ((pos > 0) && (isalpha(input[pos]) || isdigit(input[pos])))
      return (identifier(input, pos - 1));

   // Illegal character
   else
      return false;		
}

//-------------------------------------------------------------------
void test_identifier()
{
   cout << "\nTesting identifier\n";

   // Calling function
   string input[5] = { "number", "value", "x25", "y-42", "17y" };
   for (int i = 0; i < 5; i++)
   {
      cout << "identifier(" << input[i] << int(input[i].length()-1) << ") = " 
           << identifier(input[i], input[i].length()-1) << endl;
   }
}

//-------------------------------------------------------------------
const int XDIM = 25;
const int YDIM = 25;
void draw_line(char pixel[YDIM][XDIM], char color, 
   int x1, int y1, int x2, int y2)
{
   // Calculate step size
   int dx = x2 - x1;
   int dy = y2 - y1;
   int adx = abs(dx);
   int ady = abs(dy);
   int x, y;

   // Handle slope (0..1)
   if (ady < adx)
   {
      double step = double(dy) / double(dx);
      double y = y1 + 0.5;

      if (dx > 0)
         for (x=x1; x<=x2; x++, y += step)
            pixel[int(y)][x] = color;
      else
         for (x=x1; x>=x2; x--, y -= step)
            pixel[int(y)][x] = color;
   }

   // Handle slope [1..inf)
   else
   {
      double step = double(dx) / double(dy);
      double x = x1 + 0.5;

      if (dy > 0)
         for (y=y1; y<=y2; y++, x += step)
            pixel[y][int(x)] = color;
      else
         for (y=y1; y>=y2; y--, x -= step)
            pixel[y][int(x)] = color;
   }
}

//-------------------------------------------------------------------
void draw_line2(char pixel[YDIM][XDIM], char color, 
   float x1, float y1, float x2, float y2)
{
   // Draw end points
   pixel[int(0.5+y1)][int(0.5+x1)] = color;
   pixel[int(0.5+y2)][int(0.5+x2)] = color;

   // Handle recursive case
   if ((fabs(x2-x1) > 1) || (fabs(y2-y1) > 1))
   {
      float midx = (x1 + x2)/2;
      float midy = (y1 + y2)/2;
      draw_line2(pixel, color, x1, y1, midx, midy);
      draw_line2(pixel, color, midx, midy, x2, y2);
   }
}

int john = 0;
//-------------------------------------------------------------------
void flood_fill(char pixel[YDIM][XDIM], char color, int x, int y)
{
   cout << john++ << " " << x << " " << y << endl;

   // Handle terminating condition
   if ((x < 0) || (x >= XDIM) || (y < 0) || (y >= YDIM))
      return;

   else if (pixel[y][x] == color)
      return;

   // Handle recursive case
   else
   {
      pixel[y][x] = color;
      if (pixel[y][x+1] != color) flood_fill(pixel, color, x + 1, y);
      if (pixel[y][x-1] != color) flood_fill(pixel, color, x - 1, y);
      if (pixel[y+1][x] != color) flood_fill(pixel, color, x, y + 1);
      if (pixel[y-1][x] != color) flood_fill(pixel, color, x, y - 1);
   }
}

//-------------------------------------------------------------------
void print_pixel(char pixel[YDIM][XDIM])
{
   cout << "+";
   for (int x = 0; x < XDIM; x++)
      cout << "-";
   cout << "+\n";
   for (int y = 0; y < YDIM; y++)
   {
      cout << "|";
      for (int x = 0; x < XDIM; x++)
         cout << pixel[y][x];
      cout << "|\n";
   }
   cout << "+";
   for (int x = 0; x < XDIM; x++)
      cout << "-";
   cout << "+\n";
}

//-------------------------------------------------------------------
void test_flood_fill()
{
   cout << "\nTesting flood_fill\n";

   char pixel[YDIM][XDIM];
   for (int y = 0; y < YDIM; y++)
   for (int x = 0; x < YDIM; x++)
      pixel[y][x] = ' ';

   // First triangle
   draw_line(pixel, '.', 2, 2, 3, 20);
   draw_line(pixel, '.', 3, 20, 20, 15);
   draw_line(pixel, '.', 20, 15, 2, 2);
   print_pixel(pixel);
   flood_fill(pixel, '.', 5, 10);
   print_pixel(pixel);

   // Second triangle
   draw_line2(pixel, 'o', 23, 23, 22, 5);
   draw_line2(pixel, 'o', 22, 5, 5, 10);
   draw_line2(pixel, 'o', 5, 10, 23, 23);
   print_pixel(pixel);
   flood_fill(pixel, 'o', 20, 15);
   print_pixel(pixel);
}

//-------------------------------------------------------------------
int main()
{
   // test_factorial();
   // test_sum_squares();
   // test_power();
   // test_fibonacci();
   // test_ackerman();
   // test_reverse();
   // test_search();
   // test_search2();
   // test_palindrome();
   // test_tower();
   test_queen();
   // test_list_print();
   // test_identifier();
   // test_flood_fill();
}